package com.algorithm.sort;

/**
 * @program: 希尔排序
 * @author: luhd
 * @create: 2021-08-09
 */
public class ShellSort {
    public static void main(String[] args) {
        /**
         * 第一个突破O(n^2)的排序算法，是简单插入排序的改进版。
         * 它与插入排序的不同之处在于，它会优先比较距离较远的元素。
         * 希尔排序又叫缩小增量排序
         */
        int [] arr = {15,5,3,7,9 ,2,18,10,20,6};
        shellSort(arr);
    }
    public static void shellSort(int[] arr){
        int len = arr.length;
        for (int gap = len/2; gap > 0 ; gap = gap/2) {  //确定一个增量序列  gap
            for (int i = gap; i < len; i++) {
                int j = i;
                int current = arr[i];   //需要跟当前的 前第gap个相比较的 当前值
                while(j-gap >= 0 && current < arr[j-gap]){   //当 当前值 小于  前面相比较的值的时候
                    arr[j] = arr[j-gap];  //就将前面的值   换到当前值的位置
                    j = j-gap;  //当前数组下标  指向前面比较的数组下表
                }
                arr[j] = current; //当前的小值  向前移到  比较值的位置
            }
        }
        for (int i = 0; i < len; i++) {
            System.out.print(arr[i]+" ");
        }
    }
}
